{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## 4.4 \u5b9e\u73b0\u8fed\u4ee3\u5668\u534f\u8bae\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### \u95ee\u9898\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u4f60\u60f3\u6784\u5efa\u4e00\u4e2a\u80fd\u652f\u6301\u8fed\u4ee3\u64cd\u4f5c\u7684\u81ea\u5b9a\u4e49\u5bf9\u8c61\uff0c\u5e76\u5e0c\u671b\u627e\u5230\u4e00\u4e2a\u80fd\u5b9e\u73b0\u8fed\u4ee3\u534f\u8bae\u7684\u7b80\u5355\u65b9\u6cd5\u3002"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### \u89e3\u51b3\u65b9\u6848\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u76ee\u524d\u4e3a\u6b62\uff0c\u5728\u4e00\u4e2a\u5bf9\u8c61\u4e0a\u5b9e\u73b0\u8fed\u4ee3\u6700\u7b80\u5355\u7684\u65b9\u5f0f\u662f\u4f7f\u7528\u4e00\u4e2a\u751f\u6210\u5668\u51fd\u6570\u3002\n\u57284.2\u5c0f\u8282\u4e2d\uff0c\u4f7f\u7528Node\u7c7b\u6765\u8868\u793a\u6811\u5f62\u6570\u636e\u7ed3\u6784\u3002\u4f60\u53ef\u80fd\u60f3\u5b9e\u73b0\u4e00\u4e2a\u4ee5\u6df1\u5ea6\u4f18\u5148\u65b9\u5f0f\u904d\u5386\u6811\u5f62\u8282\u70b9\u7684\u751f\u6210\u5668\u3002\n\u4e0b\u9762\u662f\u4ee3\u7801\u793a\u4f8b\uff1a"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "class Node:\n    def __init__(self, value):\n        self._value = value\n        self._children = []\n\n    def __repr__(self):\n        return 'Node({!r})'.format(self._value)\n\n    def add_child(self, node):\n        self._children.append(node)\n\n    def __iter__(self):\n        return iter(self._children)\n\n    def depth_first(self):\n        yield self\n        for c in self:\n            yield from c.depth_first()\n\n# Example\nif __name__ == '__main__':\n    root = Node(0)\n    child1 = Node(1)\n    child2 = Node(2)\n    root.add_child(child1)\n    root.add_child(child2)\n    child1.add_child(Node(3))\n    child1.add_child(Node(4))\n    child2.add_child(Node(5))\n\n    for ch in root.depth_first():\n        print(ch)\n    # Outputs Node(0), Node(1), Node(3), Node(4), Node(2), Node(5)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u5728\u8fd9\u6bb5\u4ee3\u7801\u4e2d\uff0cdepth_first() \u65b9\u6cd5\u7b80\u5355\u76f4\u89c2\u3002\n\u5b83\u9996\u5148\u8fd4\u56de\u81ea\u5df1\u672c\u8eab\u5e76\u8fed\u4ee3\u6bcf\u4e00\u4e2a\u5b50\u8282\u70b9\u5e76\n\u901a\u8fc7\u8c03\u7528\u5b50\u8282\u70b9\u7684 depth_first() \u65b9\u6cd5(\u4f7f\u7528 yield from \u8bed\u53e5)\u8fd4\u56de\u5bf9\u5e94\u5143\u7d20\u3002"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### \u8ba8\u8bba\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Python\u7684\u8fed\u4ee3\u534f\u8bae\u8981\u6c42\u4e00\u4e2a __iter__() \u65b9\u6cd5\u8fd4\u56de\u4e00\u4e2a\u7279\u6b8a\u7684\u8fed\u4ee3\u5668\u5bf9\u8c61\uff0c\n\u8fd9\u4e2a\u8fed\u4ee3\u5668\u5bf9\u8c61\u5b9e\u73b0\u4e86 __next__() \u65b9\u6cd5\u5e76\u901a\u8fc7 StopIteration \u5f02\u5e38\u6807\u8bc6\u8fed\u4ee3\u7684\u5b8c\u6210\u3002\n\u4f46\u662f\uff0c\u5b9e\u73b0\u8fd9\u4e9b\u901a\u5e38\u4f1a\u6bd4\u8f83\u7e41\u7410\u3002\n\u4e0b\u9762\u6211\u4eec\u6f14\u793a\u4e0b\u8fd9\u79cd\u65b9\u5f0f\uff0c\u5982\u4f55\u4f7f\u7528\u4e00\u4e2a\u5173\u8054\u8fed\u4ee3\u5668\u7c7b\u91cd\u65b0\u5b9e\u73b0 depth_first() \u65b9\u6cd5\uff1a"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "class Node2:\n    def __init__(self, value):\n        self._value = value\n        self._children = []\n\n    def __repr__(self):\n        return 'Node({!r})'.format(self._value)\n\n    def add_child(self, node):\n        self._children.append(node)\n\n    def __iter__(self):\n        return iter(self._children)\n\n    def depth_first(self):\n        return DepthFirstIterator(self)\n\n\nclass DepthFirstIterator(object):\n    '''\n    Depth-first traversal\n    '''\n\n    def __init__(self, start_node):\n        self._node = start_node\n        self._children_iter = None\n        self._child_iter = None\n\n    def __iter__(self):\n        return self\n\n    def __next__(self):\n        # Return myself if just started; create an iterator for children\n        if self._children_iter is None:\n            self._children_iter = iter(self._node)\n            return self._node\n        # If processing a child, return its next item\n        elif self._child_iter:\n            try:\n                nextchild = next(self._child_iter)\n                return nextchild\n            except StopIteration:\n                self._child_iter = None\n                return next(self)\n        # Advance to the next child and start its iteration\n        else:\n            self._child_iter = next(self._children_iter).depth_first()\n            return next(self)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "DepthFirstIterator \u7c7b\u548c\u4e0a\u9762\u4f7f\u7528\u751f\u6210\u5668\u7684\u7248\u672c\u5de5\u4f5c\u539f\u7406\u7c7b\u4f3c\uff0c\n\u4f46\u662f\u5b83\u5199\u8d77\u6765\u5f88\u7e41\u7410\uff0c\u56e0\u4e3a\u8fed\u4ee3\u5668\u5fc5\u987b\u5728\u8fed\u4ee3\u5904\u7406\u8fc7\u7a0b\u4e2d\u7ef4\u62a4\u5927\u91cf\u7684\u72b6\u6001\u4fe1\u606f\u3002\n\u5766\u767d\u6765\u8bb2\uff0c\u6ca1\u4eba\u613f\u610f\u5199\u8fd9\u4e48\u6666\u6da9\u7684\u4ee3\u7801\u3002\u5c06\u4f60\u7684\u8fed\u4ee3\u5668\u5b9a\u4e49\u4e3a\u4e00\u4e2a\u751f\u6210\u5668\u540e\u4e00\u5207\u8fce\u5203\u800c\u89e3\u3002"
      ]
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.7.1"
    },
    "toc": {
      "base_numbering": 1,
      "nav_menu": {},
      "number_sections": true,
      "sideBar": true,
      "skip_h1_title": true,
      "title_cell": "Table of Contents",
      "title_sidebar": "Contents",
      "toc_cell": false,
      "toc_position": {},
      "toc_section_display": true,
      "toc_window_display": true
    }
  },
  "nbformat": 4,
  "nbformat_minor": 2
}